\documentclass[a4paper, 12pt, titlepage]{article}
\usepackage[cm]{fullpage}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{times}
\usepackage{cite}
\usepackage{xcolor}
\usepackage[pdftex]{graphicx}
\usepackage{indentfirst}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{listings}
\usepackage{amsmath}
\newtheorem{ru_def}{Определение}
\usepackage[pdftex, unicode]{hyperref}
 \hypersetup{
    pdfnewwindow=true,      % links in new window
    colorlinks=true,        % false: boxed links; true: colored links
    linkcolor=black,        % color of internal links
    urlcolor=blue,          % color of external links
    citecolor=black
}

%\usepackage[margin=10pt,font=small,labelfont=bf]{caption}
\usepackage{caption2}
\renewcommand{\captionlabeldelim }{.}

%\renewcommand{\thesection}{\arabic{section}.}

\graphicspath{{pics/}}

\clubpenalty=10000
\widowpenalty=10000

\begin{document}
\begin{titlepage}
\begin{center}
Санкт-Петербургский национальный исследовательский университет\\
информационных технологий, механики и оптики\\
Факультет информационных технологий и программирования\\
Кафедра <<Компьютерные Технологии>>

\vspace{10em}
\large Н. С. Буланова (группа 4539), А. С. Буздалова (группа 5538)\\
\vspace{3em}
\Large Отчет о выполнении задания по теории информации\\
<<Изучение универсальных методов сжатия на примере текстов различной длины>>\\
\vspace{3em}
\large Вариант 16\\

\vfill
\normalsize Санкт-Петербург\\
2012
\end{center}
\end{titlepage}

\sloppy
\section{Формулировка задачи исследования и исходные данные}
\subsection{Формулировка задачи}

Список алгоритмов для изучения:
\begin{enumerate}
	\item двухпроходное кодирование с использованием кода Хаффмена;			%1
	\item адаптивное кодирование с применением арифметического кодирования;	%2
	\item нумерационное кодирование;										%3
	\item алгоритм Зива-Лемпела-77 (метод скользящего словаря);				%4
	\item алгоритм Зива-Лемпела-78 (Зива-Лемпела-Велча);					%5
	\item алгоритм PPMA.													%6
\end{enumerate}

Для каждого из перечисленных методов сжатия имитировать работу алгоритма шаг за шагом, результаты выполнения алгоритма представить в виде таблицы аналогичной таблице, представленной для данного метода в \cite{info-theory}. Применить к заданной последовательности один из известных архиваторов.

\subsection{Исходные данные}
В качестве короткого текста была использована пословица <<Не узнавай друга в три дня, узнавай в три года>>. Объем текста составляет 368 бит.
Ряд алгоритмов использовался также для кодирования длинного текста, содержащегося в файле {\tt asyoulik.txt} (текст комедии Уильяма Шекспира <<As you like it>> на английском языке). Объем длинного текста составляет 1001432 бит.
\section{Метод решения}
%Расчетные формулы, комментированные листинги программ, пояснения.
Работа алгоритмов  1, 4, 5, 6 была имитирована вручную на примере короткого текста в соответствии с описаниями, приведенными в \cite{info-theory}. В качестве нумерационного кодирования было рассмотрено арифметическое нумерационное кодирование.

Алгоритмы 2 и 3 были реализованы на компьютере и применены как к короткому, так и к длинному текстам. Было рассмотрено две разновидности адаптивного кодирования: Adapt-A и Adapt-D. Исходные коды программ находятся в Приложении 2.

\section{Результаты вычислений}
%Результаты вычислений по шагам выполнения задания.

В таблицах \ref{t1} и \ref{t2} показаны результаты сжатия короткого и длинного текстов соответственно. Можно видеть, что длинный текст удалось сжать эффективнее, чем короткий. Отношение размеров исходного текста к сжатому в лучших случаях составляет 1,66 для длинного текста и 1,38 для короткого.

\begin{table}
\caption{Сравнение алгоритмов на примере короткого текста}\label{t1}
\begin{center}
\begin{tabular}{|l|l|}\hline
Метод кодирования & Затраты (бит) \\\hline
Кодирование отсутствует & 368 \\\hline
Двухпроходное кодирование с использованием кода Хаффмена & 332 \\\hline
Адаптивное кодирование A с применением арифметического кодирования & 300 \\\hline
Адаптивное кодирование D с применением арифметического кодирования & 283 \\\hline
Арифметическое нумерационное кодирование & 326 \\\hline
Алгоритм Зива-Лемпела-77(метод скользящего словаря) & 266 \\\hline
Алгоритм Зива-Лемпела-78 (Зива-Лемпела-Велча)& 279 \\\hline
Алгоритм PPMA	& 269 \\\hline
Архиватор 7zip (метод кодирования LZMA) & 368\\\hline
\end{tabular}
\end{center}
\end{table}

\begin{table}
\caption{Сравнение алгоритмов на примере длинного текста}\label{t2}
\begin{center}
\begin{tabular}{|l|l|}\hline
Метод кодирования & Затраты (бит) \\\hline
Кодирование отсутствует & 1001432 \\\hline
Адаптивное кодирование A с применением арифметического кодирования & 602631 \\\hline
Адаптивное кодирование D с применением арифметического кодирования & 602727 \\\hline
Арифметическое нумерационное кодирование & 604134 \\\hline
Архиватор 7zip (метод кодирования LZMA) & 357128\\\hline
\end{tabular}
\end{center}
\end{table}

Подробные результаты работы каждого алгоритма приведены в Приложении 1.

\section{Выводы}

Алгоритмом, наиболее эффективным для кодирования короткого текста, оказался алгоритм Зива-Лемпела-77. Также эффективен близкий к нему по объему затрат алгоритм PPMA. Использовавшийся архиватор не смог сжать предлагаемый текст.

Среди алгоритмов, примененных для кодирования длинного текста, небольшое преимущество имеет алгоритм адаптивного кодирования A. Архиватор в этом случае оказался в 1,69 раза более эффективным, чем реализованные алгоритмы.

\begin{thebibliography}{99}
\bibitem{info-theory} Кудряшов Б. Д. Теория информации: Учебник для вузов. -- СПб.: Питер, 2009. -- 320 с.
\end{thebibliography}

\newpage
\section*{Приложение 1 Результаты выполнения алгоритмов}
\subsection*{Приложение 1.1 Двухпроходное кодирование с использованием кода Хаффмена}
\includegraphics[width=\textwidth]{pic/huff-1.jpg}
\newpage
\includegraphics[width=\textwidth]{pic/huff-2.jpg}
\newpage
\subsection*{Приложение 1.2 Адаптивное кодирование с применением арифметического кодирования}
Было реализовано адаптивное кодирование (варианты A и D) с применением арифметического кодирования.\\

\subsubsection*{Результаты применения Adapt-A к короткому тексту}
Последовательность, сфомированная кодером:\\

000000000000000000000101011001010111101011111011010100010101001\\
010101010101100010111100110010101101100101110101010010101000000\\
110100101110110011000000000111010100111100001010000110001011010\\
001100000001010000111011011011100010111111001101110010010001100\\
100110010000101111111001001000011100000111010110\\

Длина на выходе: 300 бит.

\subsubsection*{Результаты применения Adapt-D к короткому тексту}
Последовательность, сфомированная кодером:\\

000000000000000000001000000110000011100001111000111110011111110
000000001111111000111001110110101110000010110110001100110011010
011101101001011111001101111100010000010000101100101011000100100
001011001101001001000110100010111100011110010111100011000101000
1010110111110100011010110000010\\

Длина на выходе: 283 бита.

\subsubsection*{Результаты применения алгоритмов к длинному тексту}
Adapt-A: длина на выходе 602631 бит\\

Adapt-D: длина на выходе 602727 бит

\begin{table}
\caption{Результаты вычислений по шагам алгоритма Adapt-A.}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}\hline
$i$ & $x_i$ & $p(x_i)$ & $q(x_i)$ & $F$ & $G$ \\\hline
0 & Н & $3.9062500\times 10^{-3}$ & 0 & $1.0000000$ & $3.9062500\times 10^{-3}$\\\hline
1 & е & $3.9215686\times 10^{-3}$ & 0 & $1.0000000$ & $7.6593137\times 10^{-6}$\\\hline
2 &   & $3.9370078\times 10^{-3}$ & $1.2598425\times 10^{-1}$ & $1.0000003$ & $1.0051592\times 10^{-8}$\\\hline
3 & у & $3.9525691\times 10^{-3}$ & 0 & $1.0000003$ & $9.9324039\times 10^{-12}$\\\hline
4 & з & $3.9682539\times 10^{-3}$ & 0 & $1.0000003$ & $7.8828602\times 10^{-15}$\\\hline
5 & н & $3.9840637\times 10^{-3}$ & 0 & $1.0000003$ & $5.2343029\times 10^{-18}$\\\hline
6 & а & $4.0000000\times 10^{-3}$ & 0 & $1.0000003$ & $2.9910302\times 10^{-21}$\\\hline
7 & в & $4.0160642\times 10^{-3}$ & 0 & $1.0000003$ & $1.5015212\times 10^{-24}$\\\hline
8 & а & $1.1111111\times 10^{-1}$ & $7.7777777\times 10^{-1}$ & $1.0000003$ & $1.6683569\times 10^{-25}$\\\hline
9 & й & $4.0322580\times 10^{-3}$ & 0 & $1.0000003$ & $6.7272456\times 10^{-29}$\\\hline
10 &   & $9.0909090\times 10^{-2}$ & $2.7272727\times 10^{-1}$ & $1.0000003$ & $6.1156778\times 10^{-30}$\\\hline
11 & д & $4.0485829\times 10^{-3}$ & 0 & $1.0000003$ & $2.0633191\times 10^{-33}$\\\hline
12 & р & $4.0650406\times 10^{-3}$ & 0 & $1.0000003$ & $6.4519046\times 10^{-37}$\\\hline
13 & у & $7.1428571\times 10^{-2}$ & $3.5714285\times 10^{-1}$ & $1.0000003$ & $4.6085033\times 10^{-38}$\\\hline
14 & г & $4.0816326\times 10^{-3}$ & 0 & $1.0000003$ & $1.2540145\times 10^{-41}$\\\hline
15 & а & $1.2500000\times 10^{-1}$ & $5.6250000\times 10^{-1}$ & $1.0000003$ & $1.5675181\times 10^{-42}$\\\hline
16 &   & $1.1764705\times 10^{-1}$ & $1.7647058\times 10^{-1}$ & $1.0000003$ & $1.8441389\times 10^{-43}$\\\hline
17 & в & $5.5555555\times 10^{-2}$ & $7.2222222\times 10^{-1}$ & $1.0000003$ & $1.0245216\times 10^{-44}$\\\hline
18 &   & $1.5789473\times 10^{-1}$ & $1.5789473\times 10^{-1}$ & $1.0000003$ & $1.6176657\times 10^{-45}$\\\hline
19 & т & $4.0983606\times 10^{-3}$ & 0 & $1.0000003$ & $3.3148888\times 10^{-49}$\\\hline
20 & р & $4.7619047\times 10^{-2}$ & $8.5714285\times 10^{-1}$ & $1.0000003$ & $1.5785185\times 10^{-50}$\\\hline
21 & и & $4.1152263\times 10^{-3}$ & 0 & $1.0000003$ & $2.9527095\times 10^{-54}$\\\hline
22 &   & $1.7391304\times 10^{-1}$ & $1.3043478\times 10^{-1}$ & $1.0000003$ & $5.1351470\times 10^{-55}$\\\hline
23 & д & $4.1666666\times 10^{-2}$ & $7.5000000\times 10^{-1}$ & $1.0000003$ & $2.1396445\times 10^{-56}$\\\hline
24 & н & $4.0000000\times 10^{-2}$ & $4.4000000\times 10^{-1}$ & $1.0000003$ & $8.5585783\times 10^{-58}$\\\hline
25 & я & $4.1322314\times 10^{-3}$ & 0 & $1.0000003$ & $1.3602317\times 10^{-61}$\\\hline
26 & , & $4.1493775\times 10^{-3}$ & $1.7842323\times 10^{-1}$ & $1.0000003$ & $2.0904130\times 10^{-65}$\\\hline
27 &   & $1.7857142\times 10^{-1}$ & $1.0714285\times 10^{-1}$ & $1.0000003$ & $3.7328804\times 10^{-66}$\\\hline
28 & у & $6.8965517\times 10^{-2}$ & $3.1034482\times 10^{-1}$ & $1.0000003$ & $2.5744003\times 10^{-67}$\\\hline
29 & з & $3.3333333\times 10^{-2}$ & $4.0000000\times 10^{-1}$ & $1.0000003$ & $8.5813344\times 10^{-69}$\\\hline
30 & н & $6.4516129\times 10^{-2}$ & $4.5161290\times 10^{-1}$ & $1.0000003$ & $5.5363447\times 10^{-70}$\\\hline
31 & а & $9.3750000\times 10^{-2}$ & $5.3125000\times 10^{-1}$ & $1.0000003$ & $5.1903232\times 10^{-71}$\\\hline
32 & в & $6.0606060\times 10^{-2}$ & $6.3636363\times 10^{-1}$ & $1.0000003$ & $3.1456504\times 10^{-72}$\\\hline
33 & а & $1.1764705\times 10^{-1}$ & $5.0000000\times 10^{-1}$ & $1.0000003$ & $3.7007652\times 10^{-73}$\\\hline
34 & й & $2.8571428\times 10^{-2}$ & $7.1428571\times 10^{-1}$ & $1.0000003$ & $1.0573614\times 10^{-74}$\\\hline
35 &   & $1.6666666\times 10^{-1}$ & $8.3333333\times 10^{-2}$ & $1.0000003$ & $1.7622691\times 10^{-75}$\\\hline
36 & в & $8.1081081\times 10^{-2}$ & $6.2162162\times 10^{-1}$ & $1.0000003$ & $1.4288668\times 10^{-76}$\\\hline
37 &   & $1.8421052\times 10^{-1}$ & $7.8947368\times 10^{-2}$ & $1.0000003$ & $2.6321232\times 10^{-77}$\\\hline
38 & т & $2.5641025\times 10^{-2}$ & $8.9743589\times 10^{-1}$ & $1.0000003$ & $6.7490338\times 10^{-79}$\\\hline
39 & р & $5.0000000\times 10^{-2}$ & $8.0000000\times 10^{-1}$ & $1.0000003$ & $3.3745169\times 10^{-80}$\\\hline
40 & и & $2.4390243\times 10^{-2}$ & $9.2682926\times 10^{-1}$ & $1.0000003$ & $8.2305291\times 10^{-82}$\\\hline
41 &   & $1.9047619\times 10^{-1}$ & $7.1428571\times 10^{-2}$ & $1.0000003$ & $1.5677198\times 10^{-82}$\\\hline
42 & г & $2.3255813\times 10^{-2}$ & $8.3720930\times 10^{-1}$ & $1.0000003$ & $3.6458600\times 10^{-84}$\\\hline
43 & о & $4.1666666\times 10^{-3}$ & 0 & $1.0000003$ & $3.4525190\times 10^{-88}$\\\hline
44 & д & $4.4444444\times 10^{-2}$ & $6.8888888\times 10^{-1}$ & $1.0000003$ & $1.5344528\times 10^{-89}$\\\hline
45 & а & $1.0869565\times 10^{-1}$ & $4.3478260\times 10^{-1}$ & $1.0000003$ & $1.6678835\times 10^{-90}$\\\hline
\end{tabular}
\end{center}
\end{table}

\begin{table}
\caption{Результаты вычислений по шагам алгоритма Adapt-D.}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}\hline
$i$ & $x_i$ & $p(x_i)$ & $q(x_i)$ & $F$ & $G$ \\\hline
0 & Н & $3.9062500\times 10^{-3}$ & 0 & $1.0000000$ & $3.9062500\times 10^{-3}$\\\hline
1 & е & $3.9215686\times 10^{-3}$ & 0 & $1.0000000$ & $7.6593137\times 10^{-6}$\\\hline
2 &   & $3.9370078\times 10^{-3}$ & $1.2598425\times 10^{-1}$ & $1.0000004$ & $1.5077389\times 10^{-8}$\\\hline
3 & у & $3.9525691\times 10^{-3}$ & 0 & $1.0000004$ & $2.9797211\times 10^{-11}$\\\hline
4 & з & $3.9682539\times 10^{-3}$ & 0 & $1.0000004$ & $5.9121452\times 10^{-14}$\\\hline
5 & н & $3.9840637\times 10^{-3}$ & 0 & $1.0000004$ & $1.1777181\times 10^{-16}$\\\hline
6 & а & $4.0000000\times 10^{-3}$ & 0 & $1.0000004$ & $2.3554363\times 10^{-19}$\\\hline
7 & в & $4.0160642\times 10^{-3}$ & 0 & $1.0000004$ & $4.7297918\times 10^{-22}$\\\hline
8 & а & $6.2500000\times 10^{-2}$ & $8.7500000\times 10^{-1}$ & $1.0000004$ & $2.9561199\times 10^{-23}$\\\hline
9 & й & $4.0322580\times 10^{-3}$ & 0 & $1.0000004$ & $5.2977059\times 10^{-26}$\\\hline
10 &   & $5.0000000\times 10^{-2}$ & $5.5000000\times 10^{-1}$ & $1.0000004$ & $2.6488529\times 10^{-27}$\\\hline
11 & д & $4.0485829\times 10^{-3}$ & 0 & $1.0000004$ & $4.3871322\times 10^{-30}$\\\hline
12 & р & $4.0650406\times 10^{-3}$ & 0 & $1.0000004$ & $7.4307795\times 10^{-33}$\\\hline
13 & у & $3.8461538\times 10^{-2}$ & $6.1538461\times 10^{-1}$ & $1.0000004$ & $2.8579921\times 10^{-34}$\\\hline
14 & г & $4.0816326\times 10^{-3}$ & 0 & $1.0000004$ & $4.5827862\times 10^{-37}$\\\hline
15 & а & $1.0000000\times 10^{-1}$ & $7.3333333\times 10^{-1}$ & $1.0000004$ & $4.5827862\times 10^{-38}$\\\hline
16 &   & $9.3750000\times 10^{-2}$ & $4.3750000\times 10^{-1}$ & $1.0000004$ & $4.2963620\times 10^{-39}$\\\hline
17 & в & $2.9411764\times 10^{-2}$ & $8.5294117\times 10^{-1}$ & $1.0000004$ & $1.2636359\times 10^{-40}$\\\hline
18 &   & $1.3888888\times 10^{-1}$ & $3.8888888\times 10^{-1}$ & $1.0000004$ & $1.7550498\times 10^{-41}$\\\hline
19 & т & $4.0983606\times 10^{-3}$ & 0 & $1.0000004$ & $2.2714191\times 10^{-44}$\\\hline
20 & р & $2.5000000\times 10^{-2}$ & $9.2500000\times 10^{-1}$ & $1.0000004$ & $5.6785479\times 10^{-46}$\\\hline
21 & и & $4.1152263\times 10^{-3}$ & 0 & $1.0000004$ & $7.2331102\times 10^{-49}$\\\hline
22 &   & $1.5909090\times 10^{-1}$ & $3.6363636\times 10^{-1}$ & $1.0000004$ & $1.1507220\times 10^{-49}$\\\hline
23 & д & $2.1739130\times 10^{-2}$ & $8.4782608\times 10^{-1}$ & $1.0000004$ & $2.5015697\times 10^{-51}$\\\hline
24 & н & $2.0833333\times 10^{-2}$ & $6.0416666\times 10^{-1}$ & $1.0000004$ & $5.2116036\times 10^{-53}$\\\hline
25 & я & $4.1322314\times 10^{-3}$ & 0 & $1.0000004$ & $6.0299546\times 10^{-56}$\\\hline
26 & , & $4.1493775\times 10^{-3}$ & $1.7842323\times 10^{-1}$ & $1.0000004$ & $7.2174688\times 10^{-59}$\\\hline
27 &   & $1.6666666\times 10^{-1}$ & $3.3333333\times 10^{-1}$ & $1.0000004$ & $1.2029114\times 10^{-59}$\\\hline
28 & у & $5.3571428\times 10^{-2}$ & $5.1785714\times 10^{-1}$ & $1.0000004$ & $6.4441685\times 10^{-61}$\\\hline
29 & з & $1.7241379\times 10^{-2}$ & $5.8620689\times 10^{-1}$ & $1.0000004$ & $1.1110635\times 10^{-62}$\\\hline
30 & н & $5.0000000\times 10^{-2}$ & $6.1666666\times 10^{-1}$ & $1.0000004$ & $5.5553177\times 10^{-64}$\\\hline
31 & а & $8.0645161\times 10^{-2}$ & $6.7741935\times 10^{-1}$ & $1.0000004$ & $4.4800949\times 10^{-65}$\\\hline
32 & в & $4.6875000\times 10^{-2}$ & $7.6562500\times 10^{-1}$ & $1.0000004$ & $2.1000445\times 10^{-66}$\\\hline
33 & а & $1.0606060\times 10^{-1}$ & $6.3636363\times 10^{-1}$ & $1.0000004$ & $2.2273199\times 10^{-67}$\\\hline
34 & й & $1.4705882\times 10^{-2}$ & $8.2352941\times 10^{-1}$ & $1.0000004$ & $3.2754704\times 10^{-69}$\\\hline
35 &   & $1.5714285\times 10^{-1}$ & $2.5714285\times 10^{-1}$ & $1.0000004$ & $5.1471679\times 10^{-70}$\\\hline
36 & в & $6.9444444\times 10^{-2}$ & $7.3611111\times 10^{-1}$ & $1.0000004$ & $3.5744221\times 10^{-71}$\\\hline
37 &   & $1.7567567\times 10^{-1}$ & $2.4324324\times 10^{-1}$ & $1.0000004$ & $6.2793902\times 10^{-72}$\\\hline
38 & т & $1.3157894\times 10^{-2}$ & $9.4736842\times 10^{-1}$ & $1.0000004$ & $8.2623556\times 10^{-74}$\\\hline
39 & р & $3.8461538\times 10^{-2}$ & $8.7179487\times 10^{-1}$ & $1.0000004$ & $3.1778290\times 10^{-75}$\\\hline
40 & и & $1.2500000\times 10^{-2}$ & $9.6250000\times 10^{-1}$ & $1.0000004$ & $3.9722863\times 10^{-77}$\\\hline
41 &   & $1.8292682\times 10^{-1}$ & $2.1951219\times 10^{-1}$ & $1.0000004$ & $7.2663774\times 10^{-78}$\\\hline
42 & г & $1.1904761\times 10^{-2}$ & $8.9285714\times 10^{-1}$ & $1.0000004$ & $8.6504493\times 10^{-80}$\\\hline
43 & о & $4.1666666\times 10^{-3}$ & 0 & $1.0000004$ & $6.7057747\times 10^{-83}$\\\hline
44 & д & $3.4090909\times 10^{-2}$ & $7.7272727\times 10^{-1}$ & $1.0000004$ & $2.2860595\times 10^{-84}$\\\hline
45 & а & $1.0000000\times 10^{-1}$ & $5.4444444\times 10^{-1}$ & $1.0000004$ & $2.2860595\times 10^{-85}$\\\hline
\end{tabular}
\end{center}
\end{table}

\newpage
\subsection*{Приложение 1.3 Арифметическое нумерационное кодирование }

\subsubsection*{Результаты применения алгоритма к короткому тексту}

Последовательность, сфомированная кодером ($\tau$, код):\\

0000000010111111110110111001111001011011011001101110100010110

0011000000000000100000000001111101000000101110111110010100011

111000110111001001011001011011100110111111110110010110011010\\

0011101011000100100110011111011100011001111001100110111111111

1101011101110011000001111000011001000111101111000100110100000

0000110100010111100101\\

Длина на выходе: 326 бит (в том числе длина $\tau$ 182 бит, длина кодового слова 144 бита).

\subsubsection*{Результаты применения алгоритма к длинному тексту}

Длина на выходе: 604134 бита (в том числе длина $\tau$ 2643 бита, длина кодового слова 601491 бит).

\begin{table}
\caption{Результаты вычислений по шагам алгоритма.}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}\hline
$i$ & $x_i$ & $p(x_i)$ & $q(x_i)$ & $F$ & $G$ \\\hline
0 & Н & $\frac{1}{46}$ & $\frac{5}{23}$ & $\frac{5}{23}$ & $\frac{1}{46}$\\\hline
1 & е & $\frac{1}{45}$ & $\frac{5}{9}$ & $\frac{95}{414}$ & $\frac{1}{2070}$\\\hline
2 &   & $\frac{9}{44}$ & $\frac{0}{1}$ & $\frac{95}{414}$ & $\frac{1}{10120}$\\\hline
3 & у & $\frac{3}{43}$ & $\frac{39}{43}$ & $\frac{899051}{3916440}$ & $\frac{3}{435160}$\\\hline
4 & з & $\frac{1}{21}$ & $\frac{4}{7}$ & $\frac{1258693}{5483016}$ & $\frac{1}{3046120}$\\\hline
5 & н & $\frac{3}{41}$ & $\frac{29}{41}$ & $\frac{129016163}{562009140}$ & $\frac{3}{124890920}$\\\hline
6 & а & $\frac{3}{20}$ & $\frac{9}{40}$ & $\frac{1474470469}{6422961600}$ & $\frac{9}{2497818400}$\\\hline
7 & в & $\frac{4}{39}$ & $\frac{14}{39}$ & $\frac{3833623241}{16699700160}$ & $\frac{3}{8117909800}$\\\hline
8 & а & $\frac{5}{38}$ & $\frac{9}{38}$ & $\frac{231759950567}{1009572782400}$ & $\frac{3}{61696114480}$\\\hline
9 & й & $\frac{2}{37}$ & $\frac{24}{37}$ & $\frac{94326299893729}{410896122436800}$ & $\frac{3}{1141378117880}$\\\hline
10 &   & $\frac{2}{9}$ & $\frac{0}{1}$ & $\frac{94326299893729}{410896122436800}$ & $\frac{1}{1712067176820}$\\\hline
11 & д & $\frac{3}{35}$ & $\frac{17}{35}$ & $\frac{660284099256919}{2876272857057600}$ & $\frac{1}{19974117062900}$\\\hline
12 & р & $\frac{3}{34}$ & $\frac{13}{17}$ & $\frac{2244965937473899}{9779327713995840}$ & $\frac{3}{679119980138600}$\\\hline
13 & у & $\frac{2}{33}$ & $\frac{10}{11}$ & $\frac{24694625312213321}{107572604853954240}$ & $\frac{1}{3735159890762300}$\\\hline
14 & г & $\frac{1}{16}$ & $\frac{15}{32}$ & $\frac{4489931874947879}{19558655427991680}$ & $\frac{1}{59762558252196800}$\\\hline
15 & а & $\frac{4}{31}$ & $\frac{8}{31}$ & $\frac{7655333846786133839}{33347507504725814400}$ & $\frac{1}{463159826454525200}$\\\hline
16 &   & $\frac{7}{30}$ & $\frac{0}{1}$ & $\frac{7655333846786133839}{33347507504725814400}$ & $\frac{1}{1984970684805108000}$\\\hline
17 & в & $\frac{3}{29}$ & $\frac{10}{29}$ & $\frac{222004681556797881499}{967077717637048617600}$ & $\frac{1}{19188049953116044000}$\\\hline
18 &   & $\frac{3}{14}$ & $\frac{0}{1}$ & $\frac{222004681556797881499}{967077717637048617600}$ & $\frac{3}{268632699343624616000}$\\\hline
19 & т & $\frac{2}{27}$ & $\frac{23}{27}$ & $\frac{52858257513523305121}{230256599437392528000}$ & $\frac{1}{1208847147046310772000}$\\\hline
20 & р & $\frac{1}{13}$ & $\frac{21}{26}$ & $\frac{9162097969010706221}{39911143902481371520}$ & $\frac{1}{15715012911602040036000}$\\\hline
21 & и & $\frac{2}{25}$ & $\frac{3}{5}$ & $\frac{24050507168653103830129}{104766752744013600240000}$ & $\frac{1}{196437661395025500450000}$\\\hline
22 &   & $\frac{5}{24}$ & $\frac{0}{1}$ & $\frac{24050507168653103830129}{104766752744013600240000}$ & $\frac{1}{942900774696122402160000}$\\\hline
23 & д & $\frac{2}{23}$ & $\frac{11}{23}$ & $\frac{2489227491955596246418357}{10843358909005407624840000}$ & $\frac{1}{10843358909005407624840000}$\\\hline
24 & н & $\frac{1}{11}$ & $\frac{15}{22}$ & $\frac{54763004823023117421203869}{238553895998118967746480000}$ & $\frac{1}{119276947999059483873240000}$\\\hline
25 & я & $\frac{1}{21}$ & $\frac{20}{21}$ & $\frac{31081705440094201779602197}{135395454485418873585840000}$ & $\frac{1}{2504815907980249161338040000}$\\\hline
26 & , & $\frac{1}{20}$ & $\frac{1}{5}$ & $\frac{5750115506417427329226406447}{25048159079802491613380400000}$ & $\frac{1}{50096318159604983226760800000}$\\\hline
27 &   & $\frac{4}{19}$ & $\frac{0}{1}$ & $\frac{5750115506417427329226406447}{25048159079802491613380400000}$ & $\frac{1}{237957511258123670327113800000}$\\\hline
28 & у & $\frac{1}{18}$ & $\frac{17}{18}$ & $\frac{1433337830316880573320284989}{6243783094236481145609400000}$ & $\frac{1}{4283235202646226065888048400000}$\\\hline
29 & з & $\frac{1}{17}$ & $\frac{10}{17}$ & $\frac{522362055536108163939411360679}{2275468701405807597503025712500}$ & $\frac{1}{72814998444985843120096822800000}$\\\hline
30 & н & $\frac{1}{16}$ & $\frac{3}{4}$ & $\frac{13372468621724368996848930833383}{58251998755988674496077458240000}$ & $\frac{1}{1165039975119773489921549164800000}$\\\hline
31 & а & $\frac{1}{5}$ & $\frac{1}{5}$ & $\frac{17366842365875803892011598484913}{75651946436348927916983712000000}$ & $\frac{1}{5825199875598867449607745824000000}$\\\hline
32 & в & $\frac{1}{7}$ & $\frac{5}{14}$ & $\frac{6240485356804705531862834388912073}{27184266086128048098169480512000000}$ & $\frac{1}{40776399129192072147254220768000000}$\\\hline
33 & а & $\frac{2}{13}$ & $\frac{3}{13}$ & $\frac{9014034404273463546024094117317439}{39266162124407180586244805184000000}$ & $\frac{1}{265046594339748468957152434992000000}$\\\hline
34 & й & $\frac{1}{12}$ & $\frac{2}{3}$ & $\frac{56164368211242349786765509500208659}{244658394775152432883525324608000000}$ & $\frac{1}{3180559132076981627485829219904000000}$\\\hline
35 &   & $\frac{3}{11}$ & $\frac{0}{1}$ & $\frac{56164368211242349786765509500208659}{244658394775152432883525324608000000}$ & $\frac{1}{11662050150948932634114707139648000000}$\\\hline
36 & в & $\frac{1}{10}$ & $\frac{3}{10}$ & $\frac{80315046542076560195074678585298382379}{349861504528467979023441214189440000000}$ & $\frac{1}{116620501509489326341147071396480000000}$\\\hline
37 &   & $\frac{2}{9}$ & $\frac{0}{1}$ & $\frac{80315046542076560195074678585298382379}{349861504528467979023441214189440000000}$ & $\frac{1}{524792256792701968535161821284160000000}$\\\hline
38 & т & $\frac{1}{8}$ & $\frac{7}{8}$ & $\frac{22999178105355416354633006634615931}{100187043415860058424562571776000000}$ & $\frac{1}{4198338054341615748281294570273280000000}$\\\hline
39 & р & $\frac{1}{7}$ & $\frac{6}{7}$ & $\frac{6746463909534431056386273001165064119891}{29388366380391310237969061991912960000000}$ & $\frac{1}{29388366380391310237969061991912960000000}$\\\hline
40 & и & $\frac{1}{6}$ & $\frac{2}{3}$ & $\frac{809575669144131726766352760139807694387}{3526603965646957228556287439029555200000}$ & $\frac{1}{176330198282347861427814371951477760000000}$\\\hline
41 &   & $\frac{1}{5}$ & $\frac{0}{1}$ & $\frac{809575669144131726766352760139807694387}{3526603965646957228556287439029555200000}$ & $\frac{1}{881650991411739307139071859757388800000000}$\\\hline
42 & г & $\frac{1}{4}$ & $\frac{1}{4}$ & $\frac{269858556381377242255450920046602564795667}{1175534655215652409518762479676518400000000}$ & $\frac{1}{3526603965646957228556287439029555200000000}$\\\hline
43 & о & $\frac{1}{3}$ & $\frac{2}{3}$ & $\frac{485745401486479036059811656083884616632201}{2115962379388174337133772463417733120000000}$ & $\frac{1}{10579811896940871685668862317088665600000000}$\\\hline
44 & д & $\frac{1}{2}$ & $\frac{1}{2}$ & $\frac{285732589109693550623418621225814480371883}{1244683752581279021843395566716313600000000}$ & $\frac{1}{21159623793881743371337724634177331200000000}$\\\hline
45 & а & $\frac{1}{1}$ & $\frac{0}{1}$ & $\frac{285732589109693550623418621225814480371883}{1244683752581279021843395566716313600000000}$ & $\frac{1}{21159623793881743371337724634177331200000000}$\\\hline
\end{tabular}
\end{center}
\end{table}

\newpage
\subsection*{Приложение 1.4 Алгоритм Зива-Лемпела-77 (метод скользящего словаря)}
\includegraphics[height=\textheight]{pic/lzw-1.jpg}

\newpage
\subsection*{Приложение 1.5 алгоритм Зива-Лемпела-78 (Зива-Лемпела-Велча)}
\includegraphics[height=\textheight]{pic/lzw-2.jpg}

\newpage
\subsection*{Приложение 1.6 Алгоритм PPMA}
\includegraphics[width=\textwidth]{pic/ppma.jpg}

\newpage
\section*{Приложение 2 Исходные коды программ}
\subsection*{Приложение 2.1 Адаптивное кодирование с применением арифметического кодирования}
\subsubsection*{Реализация адаптивного кодирования}
\begin{lstlisting}
public class AdaptiveArithmeticCoding {
	public static String code(byte[] x, boolean isDCoding) 
		throws UnsupportedEncodingException {
        final Fraction ONE = new Fraction(1, 1);
        final Fraction ZERO = new Fraction(0, 1);
		Fraction F = ZERO;
		Fraction G = ONE;

        Map<Byte, Integer> index = new HashMap<Byte, Integer>();
        List<Fraction> p = new ArrayList<Fraction>(257);
        List<Fraction> q = new ArrayList<Fraction>(257);
        List<Byte> symbols = new ArrayList<Byte>(256);

        p.add(ONE);
        q.add(ONE);

        int[] tau = new int[256];
       
		for (int i = 0; i < x.length; i++) {
            byte curr = x[i];
                       
            if (!index.containsKey(curr)) {
                //Writing escape
                F = F.add(G.multiply(q.get(0)));
                G = G.multiply(p.get(0));

                int myPosition = 0;
                for (byte s = 0; s < curr; ++s) {
                    if (!index.containsKey(s)) {
                        ++myPosition;
                    }
                }
                int mn = symbols.size();
                Fraction myP, myQ;
                myP = new Fraction(1, 256 - mn);
                myQ = new Fraction(myPosition, 256 - mn);

                //Writing the new symbol
                F = F.add(G.multiply(myQ));
                G = G.multiply(myP);

                p.add(null);
                q.add(null);
                index.put(curr, index.size() + 1);
                symbols.add(curr);
            } else {
                int code = index.get(curr);
                F = F.add(G.multiply(q.get(code)));
                G = G.multiply(p.get(code));
            }
         
            tau[curr & 255]++;

            int mn = symbols.size();
            int n = i + 1;

            if (isDCoding) {
                p.set(0, new Fraction(mn, 2 * n));
            } else {
                p.set(0, new Fraction(1, n + 1));
            }
            q.set(0, ZERO);

            for (int t = 0; t < mn; ++t) {
                byte b = symbols.get(t);
                if (isDCoding) {
                    p.set(t + 1, new Fraction(2 * tau[b & 255] - 1, 2 * n));
                } else {
                    p.set(t + 1, new Fraction(tau[b & 255], n + 1));
                }
                q.set(t + 1, q.get(t).add(p.get(t)));
            }
		}

        Fraction value = F.add(G.multiply(new Fraction(1, 2)));
		int z = G.inverse().log2up() + 1;
        StringBuilder result = new StringBuilder();
		String out = value.nBitsAfterComma(z).toString(2);
		while (result.length() + out.length() < z) {
            result.append("0");
		}
        result.append(out);
        return result.toString();
	}
	
	public static void main (String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader
			(new FileInputStream("input.txt"), "cp1251"));
        String input = in.readLine();
        in.close();
		String output = code(input.getBytes("cp1251"), true);
		System.out.println(output);
	}
\end{lstlisting}
\newpage
\subsubsection*{Ускоренный вариант адаптивного кодирования}
\begin{lstlisting}
public class FastAdaptiveArithmeticCoding {
	public static String code(byte[] x, boolean isDCoding) 
	throws UnsupportedEncodingException {
        Map<Byte, Integer> index = new HashMap<Byte, Integer>();
        List<BigInteger> p = new ArrayList<BigInteger>(257);
        List<BigInteger> q = new ArrayList<BigInteger>(257);
        List<Byte> symbols = new ArrayList<Byte>(256);

        p.add(BigInteger.ONE);
        q.add(BigInteger.ONE);

        BigInteger DIV = BigInteger.ONE;

        int[] tau = new int[256];

        BigInteger F = BigInteger.ZERO;
        BigInteger G = BigInteger.ONE;
        BigInteger localDiv = BigInteger.ONE;

		for (int i = 0; i < x.length; i++) {
            byte curr = x[i];
            
            if (!index.containsKey(curr)) {
                F = F.multiply(localDiv).add(G.multiply(q.get(0)));
                G = G.multiply(p.get(0));
                DIV = DIV.multiply(localDiv);

                int myPosition = 0;
                for (byte s = 0; s < curr; ++s) {
                    if (!index.containsKey(s)) {
                        ++myPosition;
                    }
                }
                int mn = symbols.size();
                BigInteger d = BigInteger.valueOf(256 - mn);
                
                F = F.multiply(d).add
				G.multiply(BigInteger.valueOf(myPosition)));
				
                DIV = DIV.multiply(d);

                p.add(null);
                q.add(null);
                index.put(curr, index.size() + 1);
                symbols.add(curr);
            } else {
                int code = index.get(curr);
                F = F.multiply(localDiv).add(G.multiply(q.get(code)));
                G = G.multiply(p.get(code));
                DIV = DIV.multiply(localDiv);
            }
            
            tau[curr & 255]++;

            int mn = symbols.size();
            int n = i + 1;

            if (isDCoding) {
                p.set(0, BigInteger.valueOf(mn));
                localDiv = BigInteger.valueOf(2 * n);
            } else {
                p.set(0, BigInteger.ONE);
                localDiv = BigInteger.valueOf(n + 1);
            }
            q.set(0, BigInteger.ZERO);

            for (int t = 0; t < mn; ++t) {
                byte b = symbols.get(t);
                if (isDCoding) {
                    p.set(t + 1, 
				BigInteger.valueOf(2 * tau[b & 255] - 1));
                } else {
                    p.set(t + 1, BigInteger.valueOf(tau[b & 255]));
                }
                q.set(t + 1, q.get(t).add(p.get(t)));
            }
            if ((i + 1) % 1000 == 0) {
                System.err.println((i + 1) + "/" + x.length);
            }
		}
        Fraction fG = new Fraction(G, DIV);
       
        Fraction fF = new Fraction(F, DIV);
        
        Fraction value = fF.add(fG.multiply(new Fraction(1, 2)));
       
		int z = fG.inverse().log2up() + 1;
        
        StringBuilder result = new StringBuilder();
		String out = value.nBitsAfterComma(z).toString(2);
		while (result.length() + out.length() < z) {
            result.append("0");
		}
        result.append(out);
        return result.toString();
	}
	
	public static void main (String[] args) throws IOException {
        BufferedReader in = new BufferedReader(
			new InputStreamReader(
			new FileInputStream("input-big.txt"), "cp1251"));
        StringBuilder data = new StringBuilder();
        String line;
        while ((line = in.readLine()) != null) {
            data.append(line).append("\n");
        }
        String input = data.toString();
		String output = code(input.getBytes("cp1251"), true);
		System.out.println(output);
	}
}	
\end{lstlisting}

\newpage
\subsection*{Приложение 2.2 Арифметическое нумерационное кодирование}
\subsubsection*{Реализация арифметического нумерационного кодирования}
\begin{lstlisting}
public class NumericalCoding {
	public static String code(byte[] x) 
		throws UnsupportedEncodingException {
		int[] tau = Utils.tau(x);
		int[] tauBackup = tau.clone();
		
		Fraction F = new Fraction(0, 1);
		Fraction G = new Fraction(1, 1);		
		Fraction[] p = new Fraction[Utils.size];
		Fraction[] q = new Fraction[Utils.size + 1];
		q[0] = new Fraction(0, 1);
		
		for (int i = 0; i < x.length; i++) {
			int n = x.length - i;
			
			for (int j = 1; j <= Utils.size; j++) {
				p[j - 1] = new Fraction(tau[j - 1], n);
				q[j] = q[j - 1].add(p[j - 1]);
			}
			
			int xi = x[i] & 255;
					
			F = F.add(q[xi].multiply(G));
			G = G.multiply(p[xi]);

			tau[xi]--;				
		}
		
		int z = G.inverse().log2up();
		String out = F.nBitsAfterComma(z).toString(2);
		while (out.length() < z) {
			out = "0" + out;
		}
		return Utils.tauIndex(tauBackup) + "|" + out;
	}
	
	public static void main (String[] args) throws IOException {
		String inputFileName = "input.txt";
		BufferedReader in = 
			new BufferedReader(new FileReader(inputFileName));
		String input;
		input = in.readLine();
		in.close();
		String output = code(input.getBytes("cp1251"));
		System.out.println(output);
	}
}	

\end{lstlisting}

\subsubsection*{Вычисление последовательности $\tau$ и ее номера}

\begin{lstlisting}
public class Utils {
	public final static int size = 256;
	
	public static int[] tau(byte[] x) {
		int[] tau = new int[size];		
		for (int i = 0; i < x.length; i++) {
			tau[x[i] & 255]++;
		}		
		return tau;
	}
	
	public static String tauIndex(int[] tau) {
		int n = 0;
		for (int i : tau) n += i;
		int m = tau.length;
		BigInteger index = tauIndexImpl(tau, 0, n);
		BigInteger maximum = 
			countTaus(n, m).subtract(BigInteger.ONE);
		StringBuilder rv = new StringBuilder();
		for (int t = index.bitLength(); 
			t < maximum.bitLength(); ++t) {
			rv.append("0");
		}
		if (index.signum() != 0 || 
			rv.length() < maximum.bitLength()) {
			rv.append(index.toString(2));
		}
		return rv.toString();
	}
	
	private static BigInteger 
		tauIndexImpl(int[] tau, int offset, int n) {
		int m = tau.length - offset;
		if (offset == tau.length) {
			return BigInteger.ZERO;
		}
 		BigInteger rv = BigInteger.ZERO;
		for (int t = 0; t < tau[offset]; ++t) {
			rv = rv.add(countTaus(n - t, m - 1));
		}
		return 
		rv.add(tauIndexImpl(tau, offset + 1, n - tau[offset]));
	}
	
	private static BigInteger countTaus(int n, int m) {
		return CNK.c(n + m - 1, m - 1);
	}
}
\end{lstlisting}

\subsubsection*{Ускоренный вариант арифметического нумерационного кодирования}
\begin{lstlisting}
public class FastNumericalCoding {
	public static String code(byte[] x) 
		throws UnsupportedEncodingException {
		int[] tau = Utils.tau(x);
		int[] tauBackup = tau.clone();

        BigInteger F = BigInteger.ZERO;
        BigInteger G = BigInteger.ONE;

		int[] q = new int[Utils.size + 1];
		q[0] = 0;

        BigInteger fact = BigInteger.ONE;

		for (int i = 0; i < x.length; i++) {
			int n = x.length - i;
            BigInteger N = BigInteger.valueOf(n);
			
			for (int j = 1; j <= Utils.size; j++) {
				q[j] = q[j - 1] + tau[j - 1];
			}
			
			int xi = x[i] & 255;

            F = F.multiply(N).add(
				G.multiply(BigInteger.valueOf(q[xi])));
            G = G.multiply(BigInteger.valueOf(tau[xi]));
            fact = fact.multiply(N);

			tau[xi]--;

            if ((i + 1) % 1000 == 0) {
                System.err.println((i + 1) + " / " + x.length);
            }
	}
	int z = new Fraction(fact, G).log2up();
	String out = new Fraction(F, fact).nBitsAfterComma(z).toString(2);
        StringBuilder res = 
		new StringBuilder(Utils.tauIndex(tauBackup) + "|");
        
		int newZero = 0;
        while (newZero + out.length() < z) {
			res.append("0");
            ++newZero;
		}
        res.append(out);
		return res.toString();
	}
	
	public static void main (String[] args) throws IOException {
	BufferedReader in = new BufferedReader(
	new InputStreamReader(
	new FileInputStream("input-big.txt"), "cp1251"));
        StringBuilder data = new StringBuilder();
        String line;
        while ((line = in.readLine()) != null) {
            data.append(line).append("\n");
        }
		String input = data.toString();
		in.close();
		String output = code(input.getBytes("cp1251"));
		System.out.println(output);
	}
}	
\end{lstlisting}
\end{document} 